package tree

type BPlushTreeNode struct {
	parent   *BPlushTreeNode
	KeyNum   int
	Keys     []Key
	isLeaf   bool
	Children []*BPlushTreeNode
	LeafNode *NodeLeaf
}

func (b *BPlushTreeNode) insertKeyValue(beInsertKey Key, value Value) bool {
	//不是叶子节点则插入索引
	if b.KeyNum >= M {
		return false
	}
	insertIdx := 0
	for insertIdx <= len(b.Keys)-1 {
		//相同key覆盖
		if b.Keys[insertIdx] == beInsertKey {
			if b.isLeaf {
				b.LeafNode.datas[insertIdx] = value
			}
			return true
		}
		if beInsertKey < b.Keys[insertIdx] || insertIdx > b.KeyNum-1 {
			break
		}
		insertIdx++
	}
	//可TODO 采用移位的方式插入
	//先留出空位
	copy(b.Keys[insertIdx+1:], b.Keys[insertIdx:])
	b.Keys[insertIdx] = beInsertKey
	b.KeyNum++
	if !b.isLeaf {
		return true
	}
	//是叶子节点复制data
	copy(b.LeafNode.datas[insertIdx+1:], b.LeafNode.datas[insertIdx:])
	b.LeafNode.datas[insertIdx] = value
	return true
}

func (b *BPlushTreeNode) insertNode(prePositon *BPlushTreeNode, beInsert *BPlushTreeNode) bool {
	if b.isLeaf {
		return false
	}
	insertIdx := 0
	for i, child := range b.Children {
		if child == prePositon {
			insertIdx = i + 1
			break
		}
	}
	//保存i+1 - len-1位置上的节点
	//先留出空位
	copy(b.Children[insertIdx+1:], b.Children[insertIdx:])
	b.Children[insertIdx] = beInsert
	beInsert.parent = b
	return true
}

// 移除节点中keys中的key
func (b *BPlushTreeNode) removeKey(rmKey Key) (Key, Value) {
	rmKeyIdx := 0
	found := false
	for i, key := range b.Keys {
		if rmKey == key {
			found = true
			rmKeyIdx = i
			break
		}
	}
	if !found {
		return Key(INT_MIN), Empty_Value
	}
	removedKey := b.Keys[rmKeyIdx]
	copy(b.Keys[rmKeyIdx:], b.Keys[rmKeyIdx+1:])
	// 如果是叶子节点则同时移除value
	var removedValue Value
	if b.isLeaf {
		removedValue = b.LeafNode.datas[rmKeyIdx]
		copy(b.LeafNode.datas[rmKeyIdx:], b.LeafNode.datas[rmKeyIdx+1:])
	}
	if len(b.Keys) < M {
		b.Keys = append(b.Keys, Key(INT_MIN))
	}
	b.KeyNum--
	return removedKey, removedValue
}

func MallocTreeNode(isLeaf bool, parent *BPlushTreeNode) *BPlushTreeNode {
	var newNode *BPlushTreeNode
	if isLeaf {
		newNode = &BPlushTreeNode{
			parent:   parent,
			KeyNum:   0,
			Keys:     make([]Key, M), //长度等于阶数是因为插入后需要分裂
			isLeaf:   isLeaf,
			Children: make([]*BPlushTreeNode, M+1),
			LeafNode: &NodeLeaf{
				datas: make([]Value, M),
				Next:  nil,
			},
		}
	} else {
		newNode = &BPlushTreeNode{
			parent:   parent,
			KeyNum:   0,
			Keys:     make([]Key, M), //长度等于阶数是因为插入后需要分裂
			isLeaf:   false,
			Children: make([]*BPlushTreeNode, M+1),
			LeafNode: nil,
		}
	}
	for i := range newNode.Keys {
		newNode.Keys[i] = Key(INT_MIN)
		if newNode.isLeaf {
			newNode.LeafNode.datas[i] = Empty_Value
		}
	}
	return newNode
}
